package vip.meeet.algorithm.dp;


public class Num121 {

    public static void main(String[] args) {
        int[] a = {7,1,5,3,6,4};
        int[] b = {7,6,4,3,1};
        System.out.println(maxProfit(a));
        System.out.println(maxProfit(b));
    }

    public static int maxProfit(int[] prices) {
        if(prices.length <= 1){
            return 0;
        }
        int[] med = new int[prices.length];
        for(int i=0;i<prices.length-1;i++){
            med[i] = prices[i + 1] - prices[i];
        }
        return maxSubArray(med);
    }

    public static int maxSubArray(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int[] maxi = new int[nums.length];
        int max = nums[0];
        maxi[0] = nums[0];
        for(int i=1;i<nums.length;i++){
            if(maxi[i-1] > 0){
                maxi[i] = maxi[i-1] + nums[i];
            }else {
                maxi[i] = nums[i];
            }
            if(maxi[i] > max){
                max = maxi[i];
            }
        }
        return max;
    }


}
